package com.jp.algorithm.tree;

import java.util.Stack;

public class BinarySearchTree {

    Node head;
    public BinarySearchTree(){
    }

    public Node delete(int data){
        if(head == null)
            return null;
        Node parent=null;
        Node cur=head;
        Boolean left = null;

        //查找节点，并标记父节点
        while(true){
            if(cur == null){
                return null;
            }
            if(data == cur.data){
                break;
            }else if(data <= cur.data){
                parent = cur;
                cur = cur.left;
                left = true;
            }else{
                parent = cur;
                cur = cur.right;
                left = false;
            }
        }

        //删除的是叶子节点
        if(cur.left == null && cur.right == null){
            if(cur == head){
                head = null;
            }else{
                if(left){
                    parent.left = null;
                }else{
                    parent.right = null;
                }
            }
            return cur;
        }
        //当前节点只有右子树
        if(cur.left == null && cur.right != null){

            if(cur == head){
                head = cur.right;
            }else{
                if(left){
                    parent.left = cur.right;
                }else{
                    parent.right = cur.right;
                }
            }
            cur.right=null;
            return cur;
        }
        //当前节点只有左子树
        if(cur.left != null && cur.right == null){
            if(cur == head){
                head = cur.left;
            }else{
                if(left){
                    parent.left = cur.left;
                }else {
                    parent.right = cur.left;
                }
            }
            cur.left=null;
            return cur;
        }
        //既有左子树又有右子树
        if(cur.left != null && cur.right != null){
            Node cur1 = cur.right;
            if(cur == head){
                head = cur1;
            }else{
                if(left){
                    parent.left = cur1;
                }else{
                    parent.right = cur1;
                }
            }
            while(cur1.left != null){
                cur1 = cur1.left;
            }
            cur1.left = cur.left;

            cur.left=null;
            cur.right=null;
            return cur;
        }


        return null;
    }
    public void insert(int data){
        Node node = new Node(data);
        if(head == null){
            head = node;
            return;
        }
        Node cur = head;
        while(true){
            if(data <= cur.data){
                if(cur.left == null){
                    cur.left = node;
                    return;
                }
                cur = cur.left;
            }else{
                if(cur.right == null){
                    cur.right = node;
                    return;
                }
                cur = cur.right;
            }
        }


    }


    public  Node search(int data){
        if(head == null)
            return null;
        Node cur = head;

        while(cur != null){
            if(cur.data == data){
                return cur;
            }else if(data < cur.data){
                cur = cur.left;
            }else{
                cur = cur.right;
            }
        }
        return null;
    }


    public void preTraverse(Node node){
        if(node == null)
            return;
        System.out.println("node:" + node.data);
        preTraverse(node.left);
        preTraverse(node.right);
    }
    public void midTraverse(Node node){
        if(node == null)
            return;
        midTraverse(node.left);
        System.out.println("node:" + node.data);
        midTraverse(node.right);
    }
    public void midTraverseNoRecursive(){
        Node cur = head;
        Stack<Node> stack = new Stack<>();
        while(true){
            if(cur == null){
                if(stack.isEmpty()){
                    return;
                }else{
                    Node node = stack.pop();
                    System.out.println(node.data);
                    cur = node.right;
                }
            }
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
        }
    }

    public void preTraverseNoRecursive(){
        if(head == null){
            return ;
        }
        Stack<Node> stack = new Stack<>();
        Node cur  = head;
        while(true){
            if(cur == null){
                if(stack.isEmpty()){
                    return;
                }else{
                    Node node = stack.pop();
                    cur = node.right;
                }
            }
            if(cur != null){
                System.out.println(cur.data);
                stack.push(cur);
                cur = cur.left;
            }
        }

    }
    public void afterTraverseNoRecursive(){
        if(head == null){
            return ;
        }
        Stack<Node> stack = new Stack<>();
        Node cur  = head;
        Node last = null;
        while(true){
            if(cur == null){
                if(stack.isEmpty()){
                    return;
                }else{
                    Node node = stack.peek();
                    if(node.right == null){
                        System.out.println(stack.pop().data);
                        last = node;
                        cur = null;
                    }else if(last == node.right){
                        System.out.println(stack.pop().data);
                        last = node;
                        cur = null;
                    }else {
                        cur = node.right;
                    }

                }
            }
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
        }

    }

    public void afterTraverse(Node node){
        if(node == null)
            return;
        afterTraverse(node.left);
        afterTraverse(node.right);
        System.out.println("node:" + node.data);
    }
    private class Node{
        public int data;
        public Node left;
        public Node right;

        public Node(int data){
            this.data = data;
        }
    }

    public static void testInsert(){
        BinarySearchTree binaryTree = new BinarySearchTree();
        binaryTree.init();
        binaryTree.midTraverse(binaryTree.head);
    }
    public static void testSearch(){
        BinarySearchTree binaryTree = new BinarySearchTree();
        binaryTree.init();
        System.out.println(binaryTree.search(10).data);
    }

    public static  void testPreTraverse(){
        BinarySearchTree binaryTree = new BinarySearchTree();
        binaryTree.init();
        binaryTree.preTraverse(binaryTree.head);
        System.out.println("=========================");
    }
    public static  void testAfterTraverse(){
        BinarySearchTree binaryTree = new BinarySearchTree();
        binaryTree.init();
        binaryTree.afterTraverse(binaryTree.head);
        System.out.println("=========================");
    }

    public static  void testMidTraverse(){
        BinarySearchTree binaryTree = new BinarySearchTree();
        binaryTree.midTraverse(binaryTree.head);
        System.out.println("=========================");
    }
    public static  void testMidTraverseNoRecursive(){
        BinarySearchTree binaryTree = new BinarySearchTree();
        binaryTree.init();
        binaryTree.midTraverseNoRecursive();
        System.out.println("=========================");
    }
    public static  void testPreTraverseNoRecursive(){
        BinarySearchTree binaryTree = new BinarySearchTree();
        binaryTree.init();
        binaryTree.preTraverseNoRecursive();
        System.out.println("=========================");
    }
    public static  void testAfterTraverseNoRecursive(){
        BinarySearchTree binaryTree = new BinarySearchTree();
        binaryTree.init();
        binaryTree.afterTraverseNoRecursive();
        System.out.println("=========================");
    }
    public static  void testDelete(){
        BinarySearchTree binaryTree = new BinarySearchTree();
        binaryTree.init();
        binaryTree.delete(8);
        binaryTree.midTraverse(binaryTree.head);
        System.out.println("=========================");
    }

    public void init(){
        insert(20);
        insert(30);
        insert(10);
        insert(35);
        insert(9);
        insert(11);
        insert(29);
        insert(12);
        insert(7);
        insert(8);
    }


    public static void main(String[] args) {

//        testPreTraverse();
//        testMidTraverse();
//        testAfterTraverse();
//        testSearch();
//        testInsert();
//        testDelete();
//        testMidTraverseNoRecursive();
//        testPreTraverseNoRecursive();
        testAfterTraverseNoRecursive();
    }
}
